365. 水壶问题

#leetcode/traversal/dfs #leetcode/traversal/bfs #leetcode/math

365. 水壶问题

Similar Question

Solution Tips

方案一: 模拟 + Dfs 递归

var canMeasureWater = function(c1, c2, target) {
    // 水是无限供应的, 只是两个容器
    // 在当前状态能扩展的所有状态, 对开始的时候 2 个容器都是空的
    // 只能选择往其中一个倒水, 两个都倒满水是没有意义的, 之后就不可操作了, 只能到空
    const map = new Map();
    try {
        pullWater(0, 0, target);
        return false;
    } catch (error) {
        return true;
    }

    function pullWater(w1, w2, target) {
        // w1 w2 分别当前 c1 c2 的水量

        if (map.has(`${w1}-${w2}`)) {
            // 如果已经有, 则后续的变化都是重复的
            // 而且后续的变化都不会符合题意, 直接返回即可
            // 如果符合的话直接就快速退出了, 不会记录 map
            return false;
        }

        if (w1 === target || w2 === target  || w1+w2 === target) {
            throw (true);
        }

        map.set(`${w1}-${w2}`, true);

        // 1. 把 c1 灌满
        pullWater(c1, w2, target);
        // 2. 把 c2 灌满
        pullWater(w1, c2, target);
        // 3. 把 c1 的水倒向 c2
        // 最多能倒 min(c2 - w2, w1)
        const diff2 = Math.min(c2 - w2, w1);
        pullWater(w1 - diff2, w2 + diff2, target);
        // 4. 把 c2 的水倒向 c1
        // 最多能倒 min(c1 - w1, w2)
        const diff1 = Math.min(c1 - w1, w2);
        pullWater(w1 + diff1, w2 - diff1, target);
        // 5. 把 c1 倒空
        pullWater(0, w2, target);
        // 6. 把 c2 倒空
        pullWater(w1, 0, target);
    }
};

方案二: 分析 + 数学

Loading Question... - 力扣（LeetCode）

方案三: 改写成 Bfs, 就和树是一样的

这道题其实有一道非常科学的解决方法 —— 广度遍历，我们将三个瓶子的状态标示为一个数。

然后开始拓展这个数的所有可能的状态，第一步这个数可以变为，括号里的数是上一步的数字

然后继续拓展第二步所有可能的状态，并且不得和之前的状态出现重复（这叫剪枝）

继续第三步

我们发现状态变少了，这是怎么回事呢？这是因为剪枝约束 —— 不得出现和之前重复的状态，就好比下象棋，如果我不动我还能活，但是必须动就会被将死的感觉一样。

继续第四步

继续第五步，怎么还没出现 4 这个数字呢，好着急啊！

继续第六步

总算搞定了，这就是算法的停止条件，出现第一个数字 4。所以最终的路径就是